package algorithm.recursionAndbacktrack.combination.p77;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 77. 组合
 */
class Solution_v2 {
    public List<List<Integer>> combine(int n, int k) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (n >= 0 && k >= 0 && k <= n) {
            combine(res, new LinkedList<Integer>(), n, k, 1);
        }

        System.out.println(res);
        return res;
    }

    // 求解C(n, k)， 当前已经找到的组合存储在c中，需要从start开始搜索新的元素
    private void combine(List<List<Integer>> res, LinkedList<Integer> combination, int n, int k, int start) {
        if (combination.size() == k) {
            res.add(new LinkedList<>(combination));
            return;
        }

        // 还有k-combination.size()个空位，所以[i...n]中至少要有k-combination.size()个元素
        // ==> n - i + 1 >= k - combination.size()
        // ==> i <= n - k + combination.size()) + 1

        for (int i = start; i <= n - k + combination.size() + 1; i++) {
            // 没有被遍历过
            combination.add(i);
            combine(res, combination, n, k, i + 1);
            combination.removeLast();
        }
    }

    public static void main(String[] args) {
        new Solution_v2().combine(4, 2);
    }
}